/***尚硅谷Java数据结构与java算法                   ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***双向链表                                    ***/
/***C++ 实现版本    written by Daniel           ***/
//单向链表的缺陷：
//1.只能从一个方向便利；
//2.只能从前一个节点删除本节点，不能实现自我删除；

#include <string>
#include <sstream>
#include <iostream>
#include <stack>

using std::cout;
using std::endl;
using std::stack;
using std::string;
class HeroNode
{
public:
    HeroNode(int hNum, string hName, string hNickName)
    {
        this->num = hNum;
        this->name = hName;
        this->nickName = hNickName;
    }
    HeroNode() : num(0), name(""), nickName("")
    {
    }
    string toString()
    {
        return "Hero [No=" + std::to_string(num) + "\t" + "name=" + name + +"\t"
                                                                            "nickname=" +
               nickName + "]";
    }
    int num;
    string name;
    string nickName;
    HeroNode *next = nullptr;
    HeroNode *pre = nullptr;

private:
};

//双向链表的，插入，遍历，查找，删除
class HeroNodeLinkedList
{
public:
    //尾插，头插
    void addHeadNode(HeroNode *heroNode)
    {
        if (head->next == nullptr)
        {
            tail = heroNode;
        }
        heroNode->next=head->next;
        head->next=heroNode;
        
        heroNode->pre=head;
        if (heroNode->next!=nullptr){
            heroNode->next->pre=heroNode;
        }
    }
    //尾部插入 节点
    void addTailNode(HeroNode *heroNode)
    {
        if (head->next == nullptr)
        {
            tail = head;
        }
        tail->next = heroNode;
        heroNode->pre = tail;
        tail = tail->next;
    }
    //删除节点
    void delNode(int num)
    {
        int flag = false;
        HeroNode *temp = head->next;
        while (1)
        {//最后一个节点会退出
            if (temp==nullptr){
                break;
            }
            if (temp->num==num){
                flag=true;
                temp->pre->next=temp->next;
                if (temp->next!=nullptr){
                    temp->next->pre=temp->pre;
                }
                if (temp!=nullptr){
                    delete temp;
                    temp=nullptr;
                }
                break;
            }
            temp=temp->next;
        }
        if (flag==true){
            std::cout<<"节点删除成功！"<<std::endl;
        }
        else{
            std::cout<<"节点删除失败！"<<std::endl;
        }
    }

    //双向链表正向遍历
    void print()
    {
        if (head->next == nullptr)
        {
            cout << "链表为空" << endl;
        }
        auto temp = head->next;
        while (temp != nullptr)
        {
            cout << temp->toString() << endl;
            temp = temp->next;
        }
    }
    //反向遍历
    void reversePrint()
    {
        if (head->next == nullptr)
        {
            cout << "链表为空" << endl;
        }
        auto temp = tail;
        while (temp->pre != nullptr)
        {
            cout << temp->toString() << endl;
            temp = temp->pre;
        }
    }
    ~HeroNodeLinkedList()
    {
        std::cout << "析构链表" << std::endl;
        HeroNode *temp = this->head;
        HeroNode *tempToFree;
        while (temp->next != nullptr)
        {
            tempToFree = temp;
            temp = temp->next;
            delete tempToFree;
            if (tempToFree != nullptr)
                tempToFree = nullptr;
        }
        delete temp;
        if (temp != nullptr)
            temp = nullptr;
        if (temp == nullptr)
        {
            std::cout << "析构成功" << std::endl;
        }
    }

private:
    HeroNode *head = new HeroNode();
    HeroNode *tail = nullptr;
};

int main(int argc, char **argv)
{
    HeroNode *hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode *hero2 = new HeroNode(2, "吴用", "智多星");
    HeroNode *hero3 = new HeroNode(4, "林冲", "豹子头");
    HeroNode *hero4 = new HeroNode(3, "鲁智深", "花和尚");
    HeroNode *hero5 = new HeroNode(6, "柴进", "小旋风");
    HeroNode *hero6 = new HeroNode(7, "张进", "浪里白条");
    HeroNode *hero7 = new HeroNode(3, "武松", "行者");
    HeroNodeLinkedList *heroList = new HeroNodeLinkedList();
    heroList->addHeadNode(hero1);
    heroList->addTailNode(hero2);
    heroList->addHeadNode(hero3);
    heroList->addTailNode(hero4);
    heroList->print();
    heroList->delNode(2);
    cout<<"after delete the node!\n"<<endl;
    heroList->print();
    heroList->reversePrint();
    return 0;
}